/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution74 {

    public static void main(String args[]) {
        Solution74 s = new Solution74();
        System.out.println(s.searchMatrix(new int[][]{{1}}, 1));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        int row;
        int n = matrix.length;
        int l = 0;
        int r = n - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if(matrix[mid][0] == target){
                return true;
            }
            if (matrix[mid][0] > target) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        row = l;

        l = 0;
        r = matrix[row].length - 1;
        while(l < r){
            int mid = (l + r) / 2;
            if(matrix[row][mid] == target){
                return true;
            }else if(matrix[row][mid] > target){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return matrix[row][l] == target;
    }
}
